一篇学长发的paper，简单复现一下

这篇论文总共介绍了三种RSA攻击方法。

攻击一

素数幂模：形式为$N=p^rq$，和RSA一样，安全性取决于整数分解的难度。

设$N=p^rq$是素数幂模，满足$q＜p＜2q$，有$ed-k\phi(N)=1$和$1<e<\phi(N)<N-2N^{\frac r{r+1}}+N^{\frac{r-1}{r+1}}$，我们定义$d=N^{\delta}$，如果有$\delta<\frac{1-\gamma}2$，满足：

这里的$\gamma\in (0.75,0.8)$。

根据之前了解过的legendre定理，那么对于$\frac kd$就在连分数$\frac e{N-2N^{\frac r{r+1}}+N^{\frac{r-1}{r+1}}}$展开的范围内。

知道了$d$之后，就可以把素数幂模在多项式时间内因式分解。

由于：

这两个参数进行求最大公因数，能分解出最大的因子$p^{r-1}$，$r$是已知的，所以可以得到$p$，相应的$q$也可以求解出来。

例题

1
2
3
4
5
6
7
r = 3
d = 101
# N = p ^ r * q

k = 65
N = 41285007620134480207
e = 26568872087051427501

根据上面的分析写脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import gmpy2

r = 3
d = 101
# N = p ^ r * q

k = 65
N = 41285007620134480207
e = 26568872087051427501

convergents = continued_fraction(ZZ(e) / ZZ(int(N - 2 * N ^ (r / (r + 1)) + N ^ ((r - 1) / (r + 1))))).convergents()
for c in convergents:
    k = c.numerator()
    d = c.denominator()
    if k != 0 and d != 0:
        phi = (e * d - 1) // k
        pp = gmpy2.gcd(phi, N)
        if pp != 1:
            p = gmpy2.iroot(pp, 2)[0]
            q = N // (p ^ 3)
            print(p, q)
# 82913 72431

原理证明

根据公式$ed-k\phi(N)=1$，可以得到$ed-k(p^{r-1}(p-1)(q-1))=1$。进而变形：

可以得到：

因为根据原型公式可以推得：$ed-k(N-(N-\phi(N)))=1$，所以，即可求得：

继续变形：

等式两边同时除$d(N-2N^{\frac r{r+1}}+N^{\frac{r-1}{r+1}})$，可以得到：

能知道一般满足关系$\phi(N)>\frac 23 N$和$N>6d$（根据已知的$\gamma$和$\delta$关系），那么有：

论文提到了一个引理：当满足$N=p^r q$是素幂模且$q<p<2q$和$\phi(N)=N-(p^r+p^{r-1}q-p^{r-1})$，能得到：

这个可以根据已有满足的条件进行变形得到。

根据这个引理，对之前的式子进一步变换：

已知的关系中提出了$\delta<\frac{1-\gamma}2$，也就有$\gamma-1<-2\delta$，代入：

推出这个结论之后，根据legendre定理就可以知道$k,d$是前面分式的一个连分数展开。

攻击二

当存在多组公共模数和指数时，介绍另一种攻击方式：

对于$j\ge 2$和$r\ge 2$，有$N_i=p^r_iq_i,i=1,…,j$，让$N=\min N_i$，定义几个参数：

当$1<e_i<\phi(N_i)<N_i-\triangledown$，如果存在$d<N^\delta$和$k_i<N^\delta$满足：

那么就可以通过构造矩阵LLL进行这些模数的因式分解。

例题

这里的原理比较抽象，直接拿题目来说吧。

为了说明对$j$模的攻击，考虑下面三对素数幂和指数：

1
2
3
4
5
6
N1 = 5245610482183600624272049202675113495636808362511373071 
N2 = 2759704453491798939632952241385636766809782832565746933 
N3 = 1982561833408590266295317735084327906977909011432726947 
e1 = 124578150058638136260361650334267451421573539037116160 
e2 = 189222508608287214247437091594433262438107459523793424
e3 = 177782566156085884076446917089214794069346348133984637

有$N=\min(N_i)=1982…6947$。

知道$j=3,r=3$，当$\gamma=0.75$有$\delta=\frac{j-\gamma j}{j+1}=0.1875$，$\varepsilon=\frac 14N^{\delta+\gamma-1}=0.000101009756$，定义：

构造格子：

通过LLL算法得到约减基记为$K$，计算$KM^{-1}$。

得到第一行的元素：

定义：

计算：

对于每一组数据，计算：

得到因式分解后的结果，此种RSA得以破解。

攻击三

第三种和第二种在整体思路上相似，不过第三种强调了一个当$d$和$k$都很小的情况。

第三种求解时使用了最大值的$N$，用$\gamma=0.8$和$\min e=N^\beta$，得到：

计算$C$的公式是相同的，然后造格：

后续的计算方式和第二种完全一致，计算得到$N_i$的因子，破解此种RSA。